# Definition for a binary tree node.
import collections
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        # 深度遍历 只要超过就放弃下面的
        if not root:
            return False
        a =0
        a += root.val
        if not root.left and not root.right:
            if a == sum:
                return True
            else:
                return False
        # self.hasPathSum(root.left,sum-a)
        # self.hasPathSum(root.right, sum-a)
        return self.hasPathSum(root.left, sum - a) or self.hasPathSum(root.right, sum - a)
        # deque = collections.deque()
        # a = 0
        # deque.append((root,a))
        #
        # while deque:
        #     node,val = deque.pop()
        #     val += node.val
        #     if node:
        #         if not node.left and not node.right and val == sum:
        #             return True
        #         if node.left:
        #             deque.append((node.left,val))
        #         if node.right:
        #             deque.append((node.right,val))
        # return False


m1 = TreeNode(1)
m1.left = TreeNode(2)
m1.right = TreeNode(2)
m1.right.left = TreeNode(3)
m1.right.right = TreeNode(2)
s = Solution()

t = s.hasPathSum(m1,0)
print(t)
